package woa.binarysearch;

import java.util.ArrayList;
import java.util.List;

/**
 * 找到 K 个最接近的元素
 * 给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 * 整数 a 比整数 b 更接近 x 需要满足：
 * |a - x| < |b - x| 或者 |a - x| == |b - x| 且 a < b
 *
 * 输入：arr = [1,2,3,4,5], k = 4, x = 3
 * 输出：[1,2,3,4]
 *
 * @author wangpeng
 * @date 2021/12/20
 */
public class FindClosestElements {

    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> rs = new ArrayList<>();
        int leftPos = leftSearch(arr, x);
        int rightPos = rightSearch(arr, x);
        if (leftPos == rightPos) {
            rightPos = rightPos + 1;
        }
        Integer leftRs = null, rightRs = null;
        for (int i = 0; i < k; i++) {
            if (leftRs == null && leftPos >= 0) {
                leftRs = arr[leftPos];
                leftPos--;
            }
            if (rightRs == null && rightPos > -1 && rightPos < arr.length) {
                rightRs = arr[rightPos];
                rightPos++;
            }
            if (rightRs == null || (leftRs != null && Math.abs(leftRs - x) <= Math.abs(rightRs - x))) {
                rs.add(0, leftRs);
                leftRs = null;
            } else {
                rs.add(rightRs);
                rightRs = null;
            }
        }
        return rs;
    }

    /**
     * 查找小于等于x的最大数
     *
     * @param arr
     * @param x
     * @return
     */
    public static int leftSearch(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x) {
                return mid;
            }
            if (arr[mid] > x) {
                right = mid - 1;
            } else {
                if (mid != arr.length - 1 && arr[mid + 1] <= x) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
        }
        return -1;
    }

    /**
     * 查找大于等于x的最小数
     *
     * @param arr
     * @param x
     * @return
     */
    public static int rightSearch(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x) {
                return mid;
            }
            if (arr[mid] < x) {
                left = mid + 1;
            } else {
                if (mid != 0 && arr[mid - 1] >= x) {
                    right = mid - 1;
                } else {
                    return mid;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(findClosestElements(new int[]{1,2,3,4,5}, 4, 4));
//        System.out.println(rightSearch(new int[]{2,3,4,5}, 4));
    }
}
